package com.dynamicPlanning;

/**
 * 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 *
 * 输入：
 * [1,-2,3,10,-4,7,2,-5]
 * 返回值：18
 * 说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
 */
public class FindGreatestSumOfSubArray {
    public static void main(String[] args) {
        int[] array = new int[]{1,-2,3,10,-4,7,2,-5};
        System.out.println(findGreatestSumOfSubArray2(array));
    }

    /**
     *暴力循环法
     */
    public static int findGreatestSumOfSubArray1(int[] array) {
        /**
         * 两次循环
         */
        int max = array[0];
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum = 0;
            for (int j = i; j < array.length; j++) {
                sum += array[j];
                max = Math.max(sum,max);
            }
        }
        return  max;
    }

    /**
     * 动态规划，时间复杂度O(n)，空间复杂度O(n)
     */
    public static int findGreatestSumOfSubArray2(int[] array) {
        int[] dp = new int[array.length];
        int max = array[0];
        dp[0] = array[0];
        //[1,-2,3,10,-4,7,2,-5]
        for(int i=1;i<array.length;i++){
            // 动态规划，状态转移方程，确定dp[i]的最大值
            dp[i] = Math.max(dp[i-1] + array[i], array[i]);
            // 每次比较，保存出现的最大值
            max = Math.max(max,dp[i]);
        }
        return max;
    }

    /**
     *动态规划优化：时间复杂度O(n)，空间复杂度O(1)
     */
    public static int findGreatestSumOfSubArray3(int[] array) {
        int sum = 0;
        int max = array[0];
        //[1,-2,3,10,-4,7,2,-5]
        for(int i=0;i<array.length;i++){
            // 优化动态规划，确定sum的最大值
            sum = Math.max(sum + array[i], array[i]);
            // 每次比较，保存出现的最大值
            max = Math.max(max,sum);
        }
        return max;
    }

    /**
     * 典型的动态规划。dp[n]代表以当前元素为截止点的连续子序列的最大和，
     * 如果dp[n-1]>0，dp[n]=dp[n]+dp[n-1]，因为当前数字加上一个正数一定会变大；
     * 如果dp[n-1]<0，dp[n]不变，因为当前数字加上一个负数一定会变小。
     * 使用一个变量max记录最大的dp值返回即可。
     */

    public static int findGreatestSumOfSubArray22(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            array[i] += array[i-1] > 0 ? array[i-1] : 0;
            max = Math.max(max,array[i]);
        }
        return max;
    }
}
